package j2025.j03;

import java.util.PriorityQueue;

/**
 * @Author 猫大仙
 */
public class j0323 {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }
    public ListNode merge(ListNode[] lists,int left,int right){
        if(left>right){
            return null;
        }
        if(left == right){
            return lists[left];
        }
        int mid = (right+left)/2;
        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid+1,right);

        return TwoLists(l1,l2);
    }
    public ListNode TwoLists(ListNode l1,ListNode l2){
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode head = new ListNode(0);
        ListNode prev = head;
        ListNode cur1 = l1,cur2 = l2;
        while(cur1!=null&&cur2!=null){
            if(cur1.val<=cur2.val){
                prev.next = cur1;
                cur1 = cur1.next;
                prev = prev.next;
            }else{
                prev.next = cur2;
                cur2 = cur2.next;
                prev = prev.next;
            }
        }
        if(cur1!=null){
            prev.next = cur1;

        }
        if(cur2!=null){
            prev.next = cur2;

        }
        return head.next;
    }

    PriorityQueue<ListNode> pq = new PriorityQueue<>(((o1, o2) -> {return  o1.val-o2.val;}));
    public ListNode mergeKLists2(ListNode[] lists) {
        for(ListNode node:lists){
            if(node!=null){
                pq.offer(node);
            }
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(!pq.isEmpty()){
            ListNode s = pq.poll();
            cur.next = s;
            cur=cur.next;
            s = s.next;
            if(s!=null){
                pq.offer(s);
            }
        }
        return dummy.next;
    }
}
